Cryptography is commonly used to provide data security over public networks, such as the Internet. Cryptographic protocols enable certain security goals to be achieved for various applications. A particularly efficient form of cryptography that is used in constrained devices is elliptic curve cryptography. Elliptic curve cryptography (ECC) is performed in a group of points on an elliptic curve. Such groups provide security at smaller bit sizes than alternative schemes.
The main operation in elliptic curve cryptography is so-called scalar multiplication, that is, computing an integer multiple of a point on an elliptic curve. Increases in efficiency may be obtained by increasing the speed at which elliptic curve scalar multiplication is performed. Certain elliptic curves allow faster computation because of special structure within the elliptic curve group. The special structure in the group means that there are special relationships between group elements. These relationships allow some computations to be performed more efficiently than in the general case.
One class of curves with special structure in the elliptic curve groups is those that provide a complex multiplication operation. Typically these curves are the Koblitz curves, also known as anomalous binary curves. These curves have a defining equation y2+xy=x3+a1x2+1, where a1 is either 0 or 1. The points in the elliptic curve group defined by such an equation are the points (x, y) that satisfy the equation, where x and y are elements of the finite field F2m, along with a special point called the “point at infinity.” The point at infinity operates as the zero element of the group. On a Koblitz curve, the Frobenius mapping τ:(x,y)→(x2,y2) is efficiently computable and satisfies a characteristic equation τ2+2=μτ, where μ is −1 if a is 0 and μ is 1 if a is 1. The mapping τ may be regarded as a complex number, namely the solution to the characteristic equation. Points on the curve may be multiplied by certain complex numbers that are written in terms of τ, whereas in the usual case points may only be multiplied by integers. Multiplying a point by τ corresponds to applying the Frobenius mapping to the point. In a technical report entitled Improved Algorithms for Arithmetic on Anomalous Binary Curves by Jerome Solinas, 1999, available at http://www.cacr.uwaterloo.ca, the properties of the Frobenius mapping and its use to accelerate computations are analyzed in detail.
By applying the relationship τ2+2=μτ, the degree of a polynomial in τ can be reduced. Thus, any polynomial in τ can be represented in the form A+Bτ after appropriate reduction.
The existence of complex multiplication on a curve means that scalars may be operated on modulo a truncator, T, which operates as an identity element under scalar multiplication. It can be shown that the value
  T  =                    τ        m            -      1              τ      -      1      works as a truncator. The truncator may also be expressed in the form A+Bτ by using the relationship τ2+2=μτ to obtain integers a and b such that T=a+bτ. The conjugate of the truncator T is denoted by T. The product T T is defined as the norm of T, is denoted N(T) and can be calculated as N(T)=a2+μab+2b2, an integer.
In order to compute an elliptic curve multiplication of a scalar k by a point P, Solinas teaches how to perform a modular reduction of k. The truncator T is the modulus. This method requires finding a quotient q and a remainder r satisfying the equation k=qT+r where the remainder r is as small in norm as possible. The remainder r is the result of a modular reduction of k modulo T. Solinas teaches a method of rounding off k/T and then solving for the remainder r. In this method, a quantity λ is computed as
  λ  =            k      T        .  The quantity λ is expressed in the form A+Bτ by multiplying the numerator and denominator by the complex conjugate T of T. Thus
  λ  =            k      T        =                            k          ⁢                      T            _                                    N          ⁡                      (            T            )                              .      Then the quantity λ is rounded using a special purpose rounding algorithm, referred to as Routine 60. The rounding method operates on λ based on a geometric construction that is particular to arithmetic using τ. The rounded value of λ is used as the quotient q, so that the remainder r may be computed as r=k−qT. The remainder r is the value of k reduced modulo the truncator.
It is recognized that for a truncator T, the quantity kP is equivalent to (k−qT)P for all q since TP is equal to the point at infinity, which operates as the zero element in the elliptic curve group. Certain choices of the quotient q will lead to scalars for which multiplication is faster than others. Accordingly, it is of interest to efficiently find a quotient q so that multiplication by k−qT is more efficient than multiplication by k.
The algorithm that Solinas teaches for reducing a scalar modulo the truncator requires the special purpose rounding algorithm to be executed each time a scalar multiplication is required. It optimizes based on an average case analysis and therefore requires extensive computation for each scalar multiplication. This is particularly onerous in constrained devices with limited computing power such as PDA's (Personal Digital Assistants), wireless devices, and the like.
Solinas presents a more efficient method of performing the modular reduction. It obtains an element r′ that is congruent to k modulo T, but not necessarily of minimal norm. This improvement focusses on the computation of λ. Solinas teaches computing an approximation of the coefficients of λ, then using these approximate coefficients in the special purpose rounding algorithm. However, this method still requires use of the special purpose rounding algorithm. Further, this method requires execution of the approximate division algorithm each time a scalar multiplication is performed since the quantity
  λ  =      k    T  on the scalar k.
Accordingly, there is a need for a method of performing elliptic curve scalar multiplications that obviates or mitigates at least some of the above disadvantages.